/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(head == nullptr || head->next == nullptr || head->next->next == nullptr) return;
        // 先找链表的中间结点
        ListNode* plist = new ListNode(0);
        plist->next = head;
        ListNode* fast = plist, *slow = plist;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }

        // 翻转后面链表
        ListNode* backnode = slow->next;
        slow->next = nullptr;   // 断开前面的链表
        backnode = reverseList(backnode);

        ListNode* newhead = mergeTwoLists(head, backnode);
        head = newhead;
    }

    // 翻转链表
    ListNode* reverseList(ListNode* head){
        if(head == nullptr) return head;
        ListNode* newHead = nullptr, *cur = head, *next = head->next;
        while(cur)
        {
            cur->next = newHead;
            newHead = cur;
            cur = next;
            if(next)
                next = next->next;
        }
        return newHead;
    }

    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // list1为空链表
        if(list1 == NULL)
            return list2;

        // list2为空链表
        if(list2 == NULL)
            return list1;

        // 定义两个指针分别指向list1，list2
        ListNode* l1 = list1;
        ListNode* l2 = list2;
        ListNode* newhead = new ListNode(0);   // 定义新链表
        ListNode* newtail = newhead;

        while(l1 && l2)
        {
            // 先链接list1的结点
            newtail->next = l1;
            newtail = newtail->next;
            l1 = l1->next;

            // 再链接list2的结点
            newtail->next = l2;
            newtail = newtail->next;
            l2 = l2->next;
        } 

        // list1链表没走完
        if(l1)
            newtail->next = l1;

        ListNode* rethead = newhead->next;
        delete newhead;
        
        return rethead;
    }
};